1. Field of the Invention
The present invention relates to image processing methods and apparatuses, and in particular, to an image processing method and apparatus that quantizes input data to generate binary or multilevel data, while storing the difference between an input-image density and an output-image density by using a method such as error diffusion.
2. Description of the Related Art
Error diffusion is known as a conventional pseudohalftone process that expresses input multilevel data in binary levels or a number of levels less than the levels of the input multilevel data. This error diffusion has been proposed in “An Adaptive Algorithm for Spatial Gray Scale”, Society for Information Display 1975 Symposium, Digest of Technical Papers, 1975, 36. In such an error diffusion process, when a pixel of interest is represented by P, the density of that pixel of interest is represented by v. Pixels around pixel P which are not binarized are represented by P0, P1, P2, and P3. The densities of pixels P0, P1, P2, and P3 are respectively represented by v0, v1, v2, and v3, and a threshold value for binarization is represented by T. The average density of an output image is macroscopically equalized to the density of an input image by weighting a binarized error E at pixel P using obtained weight coefficients W0, W1, W2, and W3 by experience, and allocating the obtained values to pixels P0, P1, P2, and P3, respectively.
When the output binary data is o, errors E0, E1, E2, and E3 for respective pixels P0, P1, P2, and P3 can be obtained by the following numerical expressions:If v≧T,o=1,E=v−Vmax; andIf v<T,o=0,E=v−Vmin(where Vmax represents a maximum density; and Vmin represents a minimum density); andE0=E×W0;E1=E×W1;E2=E×W2; andE3=E×W3(Examples of weight coefficients: W0= 7/16, W1= 1/16, W2= 5/16, and W3= 3/16).
Error Diffusion has the Following Problems:
Realization of the method by a logic circuit enlarges the circuit size because each weight coefficient needs a multiplier and a divider, as will be understood from the above-described example, and when an integer arithmetic operation is performed, the average density of the output image is not equal to the density of the input image due to the resultant rounding error (E−(E0+E1+E2+E3)).
Concerning methods for solving the above-described problems, Japanese Patent Laid-Open Nos. 58-215169, 61-52073, and 61-293068 have proposed that by setting weight coefficients at fractions of the powers of 2, the circuit size is reduced using shift registers in place of multipliers and dividers. Japanese Patent Laid-Open No. 63-35074 discloses that by determining pre-weighted binarized errors for density information values, and setting the total of the errors to be equal to the binarized error, simplification of multiplication and division, and elimination of rounding errors are achieved.
In addition, Japanese Patent Laid-Open No. 63-155950 has proposed that the average density of an output image is equalized to the density of an input image by adding a rounding error to weighted pixels around a pixel of interest.
Problems with these Methods are as Follows:
In the method using shift registers, flexibility is limited due to the fixing of the weight coefficients to fractions of the powers of 2. In the method in which pre-weighted binarized errors are determined and the rounding error is added to errors to be allocated to weighted pixels around the pixel of interest so that the total of the pre-weighted binarized errors is equal to the binary error, the average density of the output image is equal to the density of the input image, but the rounding error is zero or greater than at least 1 due to implementation of integer arithmetic operations. This causes deterioration in the image quality of a highlight that is easily affected by the error allocation.
Moreover, a conventional method of quantizing input multilevel data to generate data having at least three levels by using error diffusion is also known. In the case where this method is employed in an ink-jet printer, or the like, that expresses pseudo-gradations by using a plurality of inks having identical hues and different concentrations, as shown in FIG. 7, after inputting input image data to look-up tables (LUTs) 15-0 to 15-N corresponding to the respective inks for density correction, it is required that the image data be input to separate binarization circuits 16-0 to 16-N so that binarization for the inks is performed. Accordingly, a problem arises in that if the number of inks increases, the amount of processing is increased, and also the processing circuit is enlarged. A similar problem such as enlargement of the processing circuit occurs in the case of a combination of error diffusion and at least one of a recording means that uses the same type of ink and has an N-fold resolution in a main-scan direction, a recording means that has the same resolution and performs recording twice in the same dot recording position, a multidroplet method that performs recording by changing the dot diameter of ink, and a density pattern method that uses a plurality of recording dots to express one pixel.
In U.S. Pat. No. 5,621,542, an image processing method and apparatus has been proposed to eliminate the above-described problems. In this image processing method and apparatus, when input image data is quantized to generate data having at least three levels, a rounding error generated in the weighting of error data is set to be less than 1, whereby image quality, particularly highlight image quality, is increased. In the case where a plurality of inks or dots is used for pseudogradation expression, input image data is quantized to generate data having at least three levels by error diffusion using a simple circuit structure.
FIGS. 8 and 9 illustrate 4-level quantization adapted for a recording apparatus that performs recording by changing the diameter of an ink dot in three stages. FIG. 8 shows relationships among input values, errors, and output levels.
In FIG. 8, the left scale indicates a possible range of the sums of the input values and the errors, and divisions 42, 127, and 212 respectively indicate threshold values for distinguishing between output levels 0 and 1, 1 and 2, and 2 and 3, respectively. In the center column of FIG. 8, possible positive and negative ranges of errors are shown. Each black circle indicates that the indicated point is included in a range, and each blank circle indicates that the indicated point is not included in a range.
The right column of FIG. 8 shows how output levels 0, 1, 2, and 3 are output for the sums of the input values and the errors.
In FIG. 8, by way of example, the case where the sum of an input value and an error is a threshold value of 42 or less is considered. When the sum is not less than −42 and not more than 0, the output level is zero, and the sign of the error is negative. When the sum is more than zero and not more than 42, the output level is zero, and the sign of the error is positive.
In the case where the sum of an input value and an error is more than 42 and not more than a threshold value of 127, when the sum is more than 42 and not more than 85, the output level is 1, and the sign of the error is negative. When the sum is more than 85 and not more than 127, the output level is 1, and the sign of the error is positive.
FIG. 9 shows ranges in which output levels for 8-bit input values appear. In error diffusion, even if an input value has a length of eight bits, the error is between −42 and +42 when the input value is quantized to generate 4-level data, as shown in FIG. 9. Thus, outputs having different two levels appear for one input value.
By way of example, when the input value is 120, the sum of the input value and the error is not less than 78 (120−42) and not more than 162 (120+42). Accordingly, it is clear from FIG. 9 that levels 1 and 2 can appear as output values, and the frequencies of the levels 1 and 2 are 58.8% ((127−77)/(162−77)×100) and 41.2% ((160−127)/(162−77)×100), respectively.
In such error diffusion, as is clear from FIG. 9, output values for an input value are nothing but pseudoexpressions based on the appearance frequencies of two consecutive output levels. For example, the case where a pattern having consecutively changing gradations from 0 to 255 is input for quantization to 4-level data is considered. The output starts at initial level 0, and changes through the overlapping range of levels 0 and 1, the overlapping range of levels 1 and 2, and the overlapping range of levels 2 and 3, to the range of level 3 alone. Here, when a manner of arranging ink dots expressed in level 2 is considered, it is found that after ink dots expressed in level 1 are always arranged in all ink-dot positions, ink dots expressed in level 2 are alternately arranged for the level-1 dots, as shown in FIG. 10.
At this time, in the case where the difference between the densities of inks expressed in levels 1 and 2, or the difference between the diameters of the ink dots, etc., is so large as to be perceived by a human eye, a problem occurs in that the level-2 dots are arranged instead of the level-1 dots are perceived as a pseudocontour which is not preferable for the human eye. This causes a further problem in that also when an image is expressed in binary, perceptible dots suddenly appear from a certain density and the dots form a pseudocontour.